package com.cqs.leetcode.sort;

import java.util.*;

public class LastStoneWeightII1049 {

    static class Solution {
        /**
         * 贪心算法不能保证全局最优
         *
         * @param stones
         * @return
         */
        public int lastStoneWeightII(int[] stones) {
            if (stones == null || stones.length <= 0) return 0;
            //任意个数字组成的可能的和
            Set<Integer> sumComb = new HashSet<>();
            //初始化
            sumComb.add(0);
            Set<Integer> tmp = new HashSet<>();
            int sum = 0;
            //若出现相加为x的重量的组合，将sumExists[x]=true
            boolean[] sumExists = new boolean[15 * 1000 + 1];
            sumExists[0] = true;
            for (int stone : stones) {
                sum += stone;
                Iterator<Integer> iterator = sumComb.iterator();
                tmp.clear();
                while (iterator.hasNext()) {
                    int val = (iterator.next() + stone);
                    if (val < sumExists.length) {
                        sumExists[val] = true;
                        tmp.add(val);
                    }
                }
                sumComb.addAll(tmp);
            }
            for (int i = sum / 2; i >= 0; --i) {
                if (sumExists[i]) return (sum - i) - i;
            }
            return 0;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            List<int[]> list = new ArrayList<>();
//            list.add(new int[]{2,7,4,1,8,1});
            list.add(new int[]{31, 26, 33, 21, 40});
            list.forEach(it -> {
                System.out.println(solution.lastStoneWeightII(it));
            });
        }
    }
}
